
#include <stdio.h>
#include <stdbool.h>

// 定义栈的数据结构
#define MAXSIZE 100

typedef struct {
    int x, y;
} Position;

typedef struct {
    Position data[MAXSIZE];
    int top;
} Stack;

// 初始化栈
void initStack(Stack *s) {
    s->top = -1;
}

// 判断栈是否为空
bool isEmpty(Stack *s) {
    return s->top == -1;
}

// 入栈
bool push(Stack *s, Position e) {
    if (s->top == MAXSIZE - 1) {
        return false;  // 栈满，入栈失败
    }
    s->data[++s->top] = e;
    return true;
}

// 出栈
bool pop(Stack *s, Position *e) {
    if (isEmpty(s)) {
        return false;  // 栈空，出栈失败
    }
    *e = s->data[s->top--];
    return true;
}

// 打印输出
void printSolution(Stack *s, int n) {
    int i, j;
    char chessboard[n][n];
    // 初始化棋盘
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            chessboard[i][j] = '.';
        }
    }
    // 在棋盘上标记皇后位置
    for (i = 0; i <= s->top; i++) {
        Position p = s->data[i];
        chessboard[p.x][p.y] = 'Q';
    }
    // 打印棋盘
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            printf("%c ", chessboard[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

// 判断某个位置是否可以放置皇后
bool isValid(Stack *s, int x, int y) {
    int i;
    for (i = 0; i <= s->top; i++) {
        Position p = s->data[i];
        // 判断是否在同一列或者同一斜线上
        if (p.y == y || p.x + p.y == x + y || p.x - p.y == x - y) {
            return false;
        }
    }
    return true;
}

// 求解n皇后问题
void solveNQueens(int n) {
    Stack s;
    Position p;
    initStack(&s);

    int count = 0;  // 解法计数器

    int y = 0;  // 从第一列开始放置皇后
    while (true) {
        int x = s.top + 1;  // x表示下一个皇后要放置的行数
        while (x < n && y < n) {
            if (isValid(&s, x, y)) {
                p.x = x;
                p.y = y;
                push(&s, p);
                y = 0;
                break;
            }
            y++;
        }
        if (s.top == n - 1) {
            // 找到一个解
            count++;
            printSolution(&s, n);
            pop(&s, &p);
            y = p.y + 1;
        }
        if (isEmpty(&s)) {
            break;  // 所有解已找到，退出循环
        }
        if (y >= n) {
            // 当前位置无法放置皇后，回溯到上一行
            pop(&s, &p);
            y = p.y + 1;
        }
    }

    printf("共找到%d个解\n", count);
}

int main() {
    int n;
    printf("请输入皇后的数量：");
    scanf("%d", &n);
    solveNQueens(n);
    return 0;
}

